//方法一，将它展成一维的矩阵
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_len=matrix.size();
        int col_len=matrix[0].size();
        int left=0,right=col_len*row_len-1,mid=0;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(matrix[mid/col_len][mid%col_len]==target) return true;
            else if(matrix[mid/col_len][mid%col_len]>target) right=mid-1;
            else left=mid+1;
        }
        return false;
    }
};


// 方法二 贪心，每次去掉一行或者一列
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = matrix.size()-1;
        int j = 0;
        while(i>=0&&j<=matrix[0].size()-1)
        {
            if(matrix[i][j]<target) j++;
            else if(matrix[i][j]>target)i--;
            else return true;
        }
        return  false;
    }
};

